package leetcode.median;

/**
 * ClassName: $55_jump
 * Description:
 * date: 2021-11-13 10:38
 *
 * @author liyifan
 */
public class $55_jump {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 0;i < nums.length;i++) {
            for (int j = 0;j < i;j++) {
                if (j + nums[j] >= i) {
                    dp[i] = dp[j];
                }
            }
        }
        return dp[nums.length - 1];
    }
    public boolean canJump2(int[] nums) {
        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[0] = true;
        for (int i = 0;i < len;i++) {
            for (int j = 0;j < i;j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len - 1];
    }

}
